package com.yanceysong.codetop.s71_s80;

import com.yanceysong.common.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;


public class S75_Easy_234_回文链表 {
    /**
     * .回文链表判断（LeetCode 234）
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/palindrome-linked-list/">https://leetcode.cn/problems/palindrome-linked-list/</a>
     * .<p>
     * .给你一个单链表的头节点 head ，请你判断该链表是否为「回文链表」。
     * .如果是，返回 true ；否则，返回 false。
     * .<p>
     * .回文的定义：正序和逆序遍历结果完全一致。例如：
     * .[1,2,2,1] 是回文；[1,2] 不是回文；[1,2,3,2,1] 是回文。
     * .<p>
     * .核心标签：链表 / 双指针 / 快慢指针 / 反转链表
     * .可选思路：数组辅助 / 栈 / 递归（利用调用栈模拟）
     * .<p>
     * .示例1：
     * .输入：head = [1,2,2,1]
     * .输出：true
     * .解释：正序 [1,2,2,1] 逆序 [1,2,2,1]
     * .<p>
     * .示例2：
     * .输入：head = [1,2]
     * .输出：false
     * .解释：正序 [1,2] 逆序 [2,1]
     * .<p>
     * .示例3：
     * .输入：head = []
     * .输出：true （空链表通常视为回文）
     * .<p>
     * .示例4：
     * .输入：head = [1]
     * .输出：true （单节点即回文）
     * .<p>
     * .-------------------------------------------
     * .解题总览（推荐 O(1) 额外空间方案）：
     * .1. 使用快慢指针找到链表前半部分的尾节点（奇数长度时落在中点，偶数长度时落在左半部分最后一个）
     * .2. 反转后半部分链表
     * .3. 前半部分与反转后的后半部分逐节点比较
     * .4.（可选但推荐）将后半部分再次反转恢复原链表结构，保证函数“无副作用”
     * .5. 返回比较结果
     * .<p>
     * .为什么要恢复链表？
     * .- 良好的工程习惯：不改变输入数据结构，避免后续调用者产生困惑
     * .- 面试加分：体现对原始数据的尊重与副作用控制
     * .<p>
     * .快慢指针定位中点示意：
     * .链表（偶数长度示例）：1 → 2 → 3 → 4 → null
     * .slow: 走1步   fast: 走2步
     * .初始: slow=1, fast=1
     * .第1轮: slow=2, fast=3
     * .结束条件: fast.next == null 或 fast.next.next == null
     * .此时 slow=2 (前半部分尾)
     * .需要反转的后半：3 → 4
     * .<p>
     * .链表（奇数长度示例）：1 → 2 → 3 → 2 → 1 → null
     * .最终 slow 指向 3（中点），后半要反转从 slow.next 开始：2 → 1
     * .中点节点可以忽略（因为它左右对称）
     * .<p>
     * .反转后半与比较过程（示例 [1,2,3,2,1]）：
     * .原链表：1 → 2 → 3 → 2 → 1
     * .分割：  前半: 1 → 2 → 3    后半: 2 → 1
     * .反转后半：1 → 2
     * .对比： (1==1) (2==2) （前半指针第三个节点 3 与后半已经结束，比较完成）
     * .恢复：再把 1 → 2 反转回 2 → 1 拼回原状
     * .<p>
     * .ASCII 总流程：
     * .head
     * . ↓
     * .[ a1 ] → [ a2 ] → ... → [ am ] → [ b1 ] → [ b2 ] → ... → [ bk ] → null
     * .               ↑slow              ↑fast(在/越过尾部停止)
     * .Step1: 找到 slow (前半尾)
     * .Step2: 反转后半 (b1..bk) 得到 bk → ... → b2 → b1
     * .Step3: pLeft 从 head 开始，pRight 从新后半头（原bk）开始逐一比较
     * .Step4: 还原后半（再次反转）并连接回 slow.next
     * .<p>
     * .时间复杂度：O(n) （一次遍历找到中点 + 一次反转 + 一次比较 + 可选一次还原）
     * .空间复杂度：O(1) （只使用若干指针变量）
     * .<p>
     * .常见错误/陷阱：
     * .1. 奇数长度时错误地包含中点参与比较（会导致不必要的对比）
     * .2. 忘记还原链表（导致后续对链表的操作出现“异常顺序”）
     * .3. 反转逻辑中指针丢失（应提前保存 nextTemp）
     * .4. fast 指针循环条件写错导致 NullPointerException
     * .<p>
     * .关键洞察：
     * .- “只需反转后半”比“全部拷贝再比较”更节省空间
     * .- 快慢指针一次遍历即能定位分界点（无需先统计长度）
     * .- 可通过是否还原链表体现代码鲁棒性与工程意识
     * .<p>
     * .备选解法（更简单但用 O(n) 额外空间）：
     * .- 将所有节点值写入数组/列表，然后使用双指针比较头尾
     * .- 适用于快速验证或面试时先写出可行版本再优化
     */
    public boolean isPalindrome(ListNode head) {
        // 空链表或单节点直接返回 true
        if (head == null || head.next == null) {
            return true;
        }

        // 1. 找到前半部分的尾节点（slow）整个链表的中间部分
        ListNode firstHalfTail = findFirstHalfTail(head);
        // 2. 反转后半部分，得到新的后半头指针
        ListNode secondHalfHead = reverseLinkedList(firstHalfTail.next);

        // 3. 前后两段进行值比较
        ListNode pLeft = head;            // 指向前半开始
        ListNode pRight = secondHalfHead; // 指向反转后半开始（原后半尾）
        boolean isPalindrome = true;      // 标记结果，出现不等即为 false
        while (pRight != null) { // 只需遍历后半长度
            if (pLeft.val != pRight.val) {
                isPalindrome = false;
                break;
            }
            pLeft = pLeft.next;
            pRight = pRight.next;
        }

        // 4. （可选操作）还原后半部分，保持输入链表结构不变
        firstHalfTail.next = reverseLinkedList(secondHalfHead);

        return isPalindrome;
    }

    /**
     * .备选方案：使用数组辅助，空间 O(n)。保留以供对比与教学。
     * .@param head 头结点
     * .@return 是否为回文
     */
    public boolean isPalindromeArray(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        int left = 0, right = values.size() - 1;
        while (left < right) {
            if (!values.get(left).equals(values.get(right))) {
                return false;
            }
            left++; right--;
        }
        return true;
    }

    /**
     * .快慢指针找到前半部分尾节点：
     * .- 偶数长度：返回前半最后一个（如 [1,2,3,4] 返回 2）
     * .- 奇数长度：返回中点（如 [1,2,3,2,1] 返回 3）
     */
    private ListNode findFirstHalfTail(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // fast 每次走两步，slow 每次走一步
        // 终止条件保证 fast 不越界，并使 slow 落在前半尾 / 中点
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * .原地反转链表并返回新的头结点。
     */
    private ListNode reverseLinkedList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next; // 暂存下一个节点，防止链断
            curr.next = prev;              // 当前节点反向指向前一个
            prev = curr;                   // prev 前移
            curr = nextTemp;               // curr 前移
        }
        return prev; // 新的头结点（原尾）
    }

    // --------------------------- 测试代码区域 --------------------------- //

    public static void main(String[] args) {
        S75_Easy_234_回文链表 solution = new S75_Easy_234_回文链表();
        System.out.println("=== 回文链表判定测试开始 ===\n");

        // 测试1：偶数长度回文 [1,2,2,1]
        testEvenPalindrome(solution);
        // 测试2：非回文 [1,2]
        testNotPalindromeShort(solution);
        // 测试3：奇数长度回文 [1,2,3,2,1]
        testOddPalindrome(solution);
        // 测试4：单节点 [1]
        testSingleNode(solution);
        // 测试5：空链表 []
        testEmptyList(solution);
        // 测试6：大量元素构成的回文（对称构造）
        testLargePalindrome(solution);
        // 测试7：中间不同导致非回文 [1,2,3,4,2,1]
        testMiddleMismatch(solution);
        // 测试8：所有元素相同 [1,1,1,1]
        testAllSame(solution);
        // 测试9：包含负数的回文 [-1,2,-1]
        testNegativeNumbers(solution);
        // 测试10：末尾不匹配 [1,2,3,4,1]
        testTailMismatch(solution);
        // 测试11：验证调用后链表被还原（结构不变）
        testRestoreIntegrity(solution);
        // 测试12：与数组法结果对比
        testCompareArrayMethod(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    // 构建链表辅助
    private static ListNode buildList(int[] arr) {
        if (arr == null || arr.length == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode cur = head;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
        return head;
    }

    // 将链表转数组，便于断言还原性
    private static int[] toArray(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    private static void printList(String prefix, ListNode head) {
        System.out.print(prefix);
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val);
            if (cur.next != null) System.out.print(" -> ");
            cur = cur.next;
        }
        System.out.println(cur == null ? "" : "");
    }

    // ---------------- 具体测试用例 ---------------- //

    private static void testEvenPalindrome(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试1 偶数长度回文 [1,2,2,1] ---");
        ListNode head = buildList(new int[]{1,2,2,1});
        printList("原链表: ", head);
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        assert result : "偶数长度回文判定失败";
        System.out.println("✓ 通过\n");
    }

    private static void testNotPalindromeShort(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试2 非回文 [1,2] ---");
        ListNode head = buildList(new int[]{1,2});
        printList("原链表: ", head);
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: false)");
        assert !result : "非回文误判为回文";
        System.out.println("✓ 通过\n");
    }

    private static void testOddPalindrome(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试3 奇数长度回文 [1,2,3,2,1] ---");
        ListNode head = buildList(new int[]{1,2,3,2,1});
        printList("原链表: ", head);
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        assert result : "奇数长度回文判定失败";
        System.out.println("✓ 通过\n");
    }

    private static void testSingleNode(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试4 单节点 [1] ---");
        ListNode head = buildList(new int[]{1});
        printList("原链表: ", head);
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        assert result : "单节点应为回文";
        System.out.println("✓ 通过\n");
    }

    private static void testEmptyList(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试5 空链表 [] ---");
        ListNode head = buildList(new int[]{});
        printList("原链表: ", head);
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        assert result : "空链表应视为回文";
        System.out.println("✓ 通过\n");
    }

    private static void testLargePalindrome(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试6 大型回文 (长度 100) ---");
        int n = 50; // 构造 [1..50..1]
        List<Integer> vals = new ArrayList<>();
        for (int i = 1; i <= n; i++) vals.add(i);
        for (int i = n; i >= 1; i--) vals.add(i);
        int[] arr = vals.stream().mapToInt(Integer::intValue).toArray();
        ListNode head = buildList(arr);
        System.out.println("构造链表长度: " + arr.length);
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        assert result : "大型回文判定失败";
        System.out.println("✓ 通过\n");
    }

    private static void testMiddleMismatch(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试7 中间不匹配 [1,2,3,4,2,1] ---");
        ListNode head = buildList(new int[]{1,2,3,4,2,1});
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: false)");
        assert !result : "中间不匹配应为非回文";
        System.out.println("✓ 通过\n");
    }

    private static void testAllSame(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试8 全部相同元素 [1,1,1,1] ---");
        ListNode head = buildList(new int[]{1,1,1,1});
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        assert result : "全部相同元素应为回文";
        System.out.println("✓ 通过\n");
    }

    private static void testNegativeNumbers(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试9 包含负数的回文 [-1,2,-1] ---");
        ListNode head = buildList(new int[]{-1,2,-1});
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        assert result : "包含负数仍应正确判定";
        System.out.println("✓ 通过\n");
    }

    private static void testTailMismatch(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试10 尾部不匹配 [1,2,3,4,1] ---");
        ListNode head = buildList(new int[]{1,2,3,4,1});
        boolean result = solution.isPalindrome(head);
        System.out.println("isPalindrome -> " + result + " (期望: false)");
        assert !result : "尾部不匹配应为非回文";
        System.out.println("✓ 通过\n");
    }

    private static void testRestoreIntegrity(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试11 结构还原验证 --- 构造回文并调用后检查链表顺序是否保持");
        int[] original = {1,2,3,2,1};
        ListNode head = buildList(original);
        int[] before = toArray(head);
        boolean result = solution.isPalindrome(head);
        int[] after = toArray(head);
        System.out.println("isPalindrome -> " + result + " (期望: true)");
        System.out.println("调用前后数组是否一致: " + Arrays.equals(before, after));
        assert Arrays.equals(before, after) : "链表结构未恢复";
        System.out.println("✓ 结构还原验证通过\n");
    }

    private static void testCompareArrayMethod(S75_Easy_234_回文链表 solution) {
        System.out.println("--- 测试12 与数组法结果对比 ---");
        int[][] cases = {
                {1,2,2,1}, {1,2}, {1,2,3,2,1}, {1}, {}, {1,1,1,1}, {-1,2,-1}, {1,2,3,4,1}
        };
        for (int[] c : cases) {
            ListNode head = buildList(c);
            boolean r1 = solution.isPalindrome(head);
            boolean r2 = solution.isPalindromeArray(head); // 数组法不破坏结构
            System.out.println("Case " + Arrays.toString(c) + " -> O(1)法:" + r1 + ", 数组法:" + r2);
            assert r1 == r2 : "两种算法结果不一致";
        }
        System.out.println("✓ 对比一致\n");
    }
}
